﻿using System;
using System.Collections.Generic;
using System.Text;
using GraphAPI;
using GraphAPI.Model;
using System.Drawing;

namespace Diameter
{
	public class DiameterAlg : IAlgorithm
	{

		#region IAlgorithm Members

		public string Category
		{
			get
			{
				return "";
			}
		}

		public string Description
		{
			get
			{
				return "Подсчёт диаметра графа";
			}
		}

		public string Name
		{
			get
			{
				return "Диаметр графа";
			}
		}

		public System.Windows.Forms.Control Use(GraphAPI.Model.Graph graph)
		{
			int a = 0, b = 0, length = 0;
			for (int i = 0; i < graph.EntityCount - 1; i++)
			{
				for (int j = i + 1; j < graph.EntityCount; j++)
				{
					int wayLength = Math.Max(GetWay(graph, i, j).Count, GetWay(graph, j, i).Count);
					if (wayLength > length)
						length = wayLength;
				}
			}

			DiameterPanel panel = new DiameterPanel();

			Graph editedGraph = FindWay(graph, a, b);

			panel.resultLabel.Text = (graph.EntityCount==0) ? "граф пуст" : "Диаметр = " + ((graph.RelationCount==0) ? "0" : (length - 1).ToString());

			panel.graphPanel.Graph = editedGraph;

			return panel;
		}

		#endregion


		private List<int> GetWay(Graph g, int from, int to)
		{
			bool[,] m = g.RelationMatrix;

			int[] d = new int[g.EntityCount];
			int st = 0;

			for (int i = 0; i < g.EntityCount; i++)
				d[i] = -1;
			d[from] = 0;
			
			int x = 0;
			do //Делаем шаги
			{
				st++;
				x = 0;

				for (int i = 0; i < g.EntityCount; i++)
				{ //Ищем вершины, из которых будем делать шаг
					if (d[i] == st - 1)
					{	// Смотрим куда можно шагнуть
						for (int j = 0; j < g.EntityCount; j++)
						{
							// Собсно шаг - отмечаем расстояние до вершины
							if (d[j] == -1 && m[i, j] == true)
							{
								d[j] = st;
								x++;
							}
						}
					}
				}

				if (d[to] != -1)
					break;
			}
			while (x > 0);

			List<int> way = new List<int>();
			if (d[to] != -1)
			{
				way.Add(to);
				int cur = to;
				while (cur != from)
				{
					st--;
					for (int j = 0; j < g.EntityCount; j++)
					{
						if (d[j] == st && m[j, cur] == true)
						{
							cur = j;
							way.Add(j);
							break;
						}
					}
				}
			}
			return way;
		}
		private Graph FindWay(Graph g, int from, int to)
		{
			if (g.EntityCount == 0)
			{
				return g;
			}

			bool[,] m = g.RelationMatrix;

			int[] d = new int[g.EntityCount];
			int st = 0;

			for (int i = 0; i < g.EntityCount; i++)
				d[i] = -1;
			d[from] = 0;

			int x = 0;
			do //Делаем шаги
			{
				st++;
				x = 0;

				for (int i = 0; i < g.EntityCount; i++)
				{ //Ищем вершины, из которых будем делать шаг
					if (d[i] == st - 1)
					{	// Смотрим куда можно шагнуть
						for (int j = 0; j < g.EntityCount; j++)
						{
							// Собсно шаг - отмечаем расстояние до вершины
							if (d[j] == -1 && m[i, j] == true)
							{
								d[j] = st;
								x++;
							}
						}
					}
				}

				if (d[to] != -1)
					break;
			}
			while (x > 0);

			List<int> way = new List<int>();
			if (d[to] != -1)
			{
				way.Add(to);
				int cur = to;
				while (cur != from)
				{
					st--;
					for (int j = 0; j < g.EntityCount; j++)
					{
						if (d[j] == st && m[j, cur] == true)
						{
							cur = j;
							way.Add(j);
							break;
						}
					}
				}
			}

			Graph result = new Graph(g);
			Relation rel;
			int oldI = -1;

			foreach (int i in way)
			{
				result.Entitys[i].ColorMark = Color.Gray;
				if (oldI > -1)
				{
					rel = result.FindRelation(result.Entitys[i], result.Entitys[oldI]);
					rel.ColorMark = Color.Aqua;
				}

				oldI = i;
			}

			if (d[to] != -1)
			{
				result.Entitys[from].ColorMark = Color.DarkGray;
				result.Entitys[to].ColorMark = Color.DarkGray;
			}
			return result;
		}
	}
}
